"""
   author: 陈亚敏
   data: 2021/11/21  10:23
   project: 1
"""

def quicksort(array):
    recurse(array,0,len(array)-1)
    return array

def recurse(array,star,end):
    if star>=end:
        return
    p=star
    left=star+1
    right=end
    while left<=right:
        if array[left]>array[p] and array[right]<array[p]:
            array[left],array[right]=array[right],array[left]
        if array[left]<=array[p]:
            left+=1
        if array[right]>=array[p]:
            right-=1
    array[p],array[right]=array[right],array[p]

    list_left=right-star
    list_right=end-left
    if list_left<list_right:
        recurse(array,star,right-1)
        recurse(array,right+1,end)
    else:
        recurse(array, right + 1, end)
        recurse(array, star, right - 1)


array=[9,4,6,1,2,5]
print(quicksort(array))